(1) Field of the Invention
The present invention relates to a packet forwarding device connected to a packet forwarding network, and more specifically to a traffic shaping unit provided within the packet forwarding device.
(2) Description of the Related Art
The packets are different in length every protocols. There are known those variable in length every packets as in the case of an IP (Internet Protocol) and those each having a fixed length as in an ATM (Asynchronous Transfer Mode). Low-cost services have recently been applied to a public packet network. Attention has been focused on a Virtual Private Network (VPN) wherein a plurality of private networks are connected to one another through a public packet network.
The packets are different in length depending on the protocol. There are known those protocols in which every packet is variable in length, as in the case of an IP (Internet Protocol), and those in which each packet has a fixed length, as in an ATM (Asynchronous Transfer Mode) protocol. Additionally, low-cost services have recently been applied to a public packet network, and attention has been focused on a Virtual Private Network (VPN) wherein a plurality of private networks are connected to one another through a public packet network.
A diagram of connections between enterprise networks through a public network is shown in FIG. 2.
In FIG. 2, a private network A41 and a private network B42 are connected to each other through a public network 40. When communications are carried out through a public network, each user normally makes a contract for a transmission bandwidth and packet forwarding priorities with a manager for the public network before packet forwarding.
When the contract is established between each of the users and the public network manager and a terminal starts to transfer or forward packets to the public network, a packet forwarding device 402 located at the entrance of the public network monitors a transmission bandwidth for each terminal in order to make lower the priority of packets from a terminal which violates the contents of the contract or to discard violation packets. This monitoring function on the public network side will be referred to as UPC (Usage Parameter Control). Even if a packet is discarded in the course of communications, a receiving terminal is normally provided with the function of recognizing the occurrence of a packet discard and requesting a packet retransmission to a transmitting terminal, whereas the transmitting terminal is provided with the function of retransmitting the packet. Therefore, there is no omission of information in final. However, it is desirable to avoid the occurrence of the packet discard because this could lead to a great increase in transfer delay and a congestion of networks due to retransmitted packets.
Thus, a packet forwarding device 401, which is transmitting packets to the public network, needs to transmit the packets under the control of a transmission bandwidth in such a manner that the packets will not be discarded by UPC of the public network. The function of controlling this packet transmission bandwidth is referred to as traffic shaping function or simply called shaping function. There may be cases in which a shaping unit for implementing the shaping function is required for a user's transmitting terminal or an exit portion of a public network for transmitting packets to a private network as well as for the above-described packet forwarding device directly connected to the public network.
The service provided for each user by the public network, i.e., the contract established between the user and the public network manager is roughly classified into a contract under which packet are transmitted after a predetermined bandwidth is always ensured within the public network, and a best effort type contract under which packets are forwarded without ensuring a bandwidth within a public ATM network. The former is suitable for the transfer of voice or the like because the packet can be always transferred at a predetermined bandwidth without being affected by the volume of traffic for other users within the public network. The latter is normally cheaper than a fixed bandwidth contract although a transfer delay might increase depending on the volume of traffic for other users or packets might be discarded within the network. This has been used for the transfer of burst data or outbreak data traffics such as FTP (File Transfer Protocol), an electronic mail, etc.
There has recently been proposed a class which guarantees a predetermined bandwidth even when a public network is busy, while it is the best effort type contract. This is called “GFR (Guaranteed Frame Rate)” in ATM. In this class, the minimum guaranteed bandwidth and the maximum transfer bandwidth are contracted before the transfer of packets. When the public network is not busy, the packets are forwarded at the maximum transfer bandwidth, whereas packets corresponding to the minimum guaranteed bandwidth is surely transferred even when the network becomes busy.
A method of implementing the shaping unit has been described in, for example, “Traffic Shaping Unit” disclosed in Japanese Published Unexamined Patent Application No. Hei 9-307566 (Prior Art 1). The Prior Art 1 has described an ATM. A fixed-length packet employed in the ATM is generally referred to as “cell” in particular. In the Prior Art 1, queues are provided every contract units (e.g., VC: Virtual Connections) at which it is desired to perform shaping. Upon transmission of cells, a time at which the next cell can be transmitted at a cell-transmitted VC (hereinafter called “scheduled transmission time”), is calculated and stored by using a binary tree structure.
In this case, scheduled transmission times at respective VC are stored at the bottom of a binary tree. Further, VC at earlier scheduled transmission times, which correspond to those lying in the past on a time basis, go up while surpassing others, and VC at the earliest scheduled transmission time is finally selected. Thus, a scheduled transmission time, which correspond to one of values at the bottom of the binary tree, for VC to be transmitted with the highest priority is stored at the top of the binary tree.
The calculation and sorting of each scheduled transmission time are carried out even when a cell is received in a transmit-wait cell-free state as well as upon cell transmission. Thus, since the sorting can be performed using a sorting result indicated by the binary tree structure at the preceding cell transmission, VC to be transmitted with the highest priority can be selected in a processing time of the order of log{VC number}.
Important packets and packets not important in particular exist in mixed form within packets which have been transmitted to a communication path or channel. Here, the important packets are packets for traffics needed for low delay transfer, such as “telnet”, etc., whereas the packets not important so far are packets for traffics, which are placed under a less influence even if the delay increases as in the case of the electronic mail.
It is important to perform such priority control that when the important packets and the packets not important so far exist in mixed form in this way, the important packets are preferentially transmitted ahead of others even when the network is being congested. Therefore, a header of the normal packet includes a field for indicating the priority of the packet. For example, a TOS (Type of Service) field is prepared for an IP packet, whereas a CLP (Cell Loss Priority) bit is prepared for an ATM cell. Incidentally, the priority will be explained hereinafter as two stages, high priority and low priority, in the interest of simplicity. However, each IP packet can be also given a further detailed priority. Further, a packet to which a high priority is assigned, will be described as a high priority packet, and a packet to which a low priority is assigned, will be described as a low priority packet.
When the conventional shaping unit is applied to the best effort type service which carries out a bandwidth guarantee, all the packets are transmitted with high priority. Each high priority packet, which has exceeded the guarantee bandwidth, is lowered in priority by the UPC function. Since, at this time, the high priority packet and low priority packet are determined without taking into consideration the above-described important packets or non-important packets, an important “telnet” packet might be assigned to the low priority packet or a Web packet not important in particular might be assigned to the high priority packet. This is not a desirable priority assignment to users.
It is easy to assign the important packets to the high priority packets and assign the non-important packets to the low priority packets within the shaping unit. However, if shaping is not carried out in such a manner that the transmission bandwidth for high priority packets falls below the guaranteed bandwidth, then the priority is lowered at random by UPC. Therefore, this is not a desirable priority assignment to the users either. Further, when the volume of traffic for important packets is small, the guaranteed bandwidth cannot be effectively utilized. It is of importance that since a chief object to perform accounting is the guaranteed bandwidth, the guaranteed bandwidth is effectively utilized to the fullest.